package 栈;

import java.util.Stack;

/**
 * @author liucong
 * @date 2021/2/24 - 10:31
 *
 * 实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "1 + 1"
 * 输出：2
 * 示例 2：
 *
 * 输入：s = " 2-1 + 2 "
 * 输出：3
 * 示例 3：
 *
 * 输入：s = "(1+(4+5+2)-3)+(6+8)"
 * 输出：23
 *  
 *
 * 提示：
 *
 * 1 <= s.length <= 3 * 105
 * s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
 * s 表示一个有效的表达式
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/basic-calculator
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _224_基本计算器 {
    public static void main(String[] args) {
        String s = "(1+(4+5+2)-3)+(6+8)";
        System.out.println(calculate(s));
    }

    public static int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        int res = 0;
        int sign = 1; //数字的正负
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(Character.isDigit(ch)){
                num = num * 10 + (ch - '0');
            }else if(ch == '+'){
                res += sign * num;
                sign = 1;
                num = 0;
            }else if(ch == '-'){
                res += sign * num;
                sign = -1;
                num = 0;
            }else if(ch == '('){
                stack.push(res);
                stack.push(sign);
                sign = 1;
                res = 0;
            }else if(ch == ')'){
                res += sign * num;
                res *= stack.pop();
                res += stack.pop();
                num = 0;
            }
        }
        return res + sign * num;
    }

//    class Solution {
//        public int calculate(String s) {
//            Stack<Integer> stack = new Stack<Integer>();
//            int operand = 0;
//            int result = 0; // For the on-going result
//            int sign = 1;  // 1 means positive, -1 means negative
//
//            for (int i = 0; i < s.length(); i++) {
//
//                char ch = s.charAt(i);
//                if (Character.isDigit(ch)) {
//
//                    // Forming operand, since it could be more than one digit
//                    operand = 10 * operand + (int) (ch - '0');
//
//                } else if (ch == '+') {
//
//                    // Evaluate the expression to the left,
//                    // with result, sign, operand
//                    result += sign * operand;
//
//                    // Save the recently encountered '+' sign
//                    sign = 1;
//
//                    // Reset operand
//                    operand = 0;
//
//                } else if (ch == '-') {
//
//                    result += sign * operand;
//                    sign = -1;
//                    operand = 0;
//
//                } else if (ch == '(') {
//
//                    // Push the result and sign on to the stack, for later
//                    // We push the result first, then sign
//                    stack.push(result);
//                    stack.push(sign);
//
//                    // Reset operand and result, as if new evaluation begins for the new sub-expression
//                    sign = 1;
//                    result = 0;
//
//                } else if (ch == ')') {
//
//                    // Evaluate the expression to the left
//                    // with result, sign and operand
//                    result += sign * operand;
//
//                    // ')' marks end of expression within a set of parenthesis
//                    // Its result is multiplied with sign on top of stack
//                    // as stack.pop() is the sign before the parenthesis
//                    result *= stack.pop();
//
//                    // Then add to the next operand on the top.
//                    // as stack.pop() is the result calculated before this parenthesis
//                    // (operand on stack) + (sign on stack * (result from parenthesis))
//                    result += stack.pop();
//
//                    // Reset the operand
//                    operand = 0;
//                }
//            }
//            return result + (sign * operand);
//        }
//    }
}
